﻿//给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。
//你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
//
//以任意顺序返回这两个数字均可。
//
//输入：[1]
//输出：[2,3]
//
//输入：[2,3]
//输出：[1,4]
//
//提示：
//	nums.length <= 30000

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        // 1.将所有的数异或在⼀起

        int tmp = 0;
        for (auto x : nums)
            tmp ^= x;
        for (int i = 1; i <= nums.size() + 2; i++)
            tmp ^= i;
        // 2.找出a,b中⽐特位不同的那⼀位

        int diff = 0;
        while (1) {
            if (((tmp >> diff) & 1) == 1)
                break;
            else
                diff++;
        }
        // 3.根据diff位的不同，将所有的数划分为两类来异或

        int a = 0, b = 0;
        for (int x : nums)
            if (((x >> diff) & 1) == 1)
                b ^= x;
            else
                a ^= x;
        for (int i = 1; i <= nums.size() + 2; i++)
            if (((i >> diff) & 1) == 1)
                b ^= i;
            else
                a ^= i;
        return { a, b };
    }
};